// https://leetcode.cn/problems/reconstruct-itinerary/
package leet332reconstructitinerary

import "sort"

// 思路
// 1. 使用DFS遍历所有可能的路径
// 2. 使用字典存储每个机场的出发地和目的地
// 3. 使用优先队列（最小堆）来保证字典序最小
// 4. 回溯法来找到所有可能的路径
func findItinerary(tickets [][]string) []string {
	// graph的作用是
	graph := make(map[string][]string)
	for _, ticket := range tickets {
		from, to := ticket[0], ticket[1]
		graph[from] = append(graph[from], to)
	}

	// 对每个出发地的目的地进行排序，保证字典序最小
	for from := range graph {
		sort.Strings(graph[from])
	}

	var result []string
	var dfs func(string)
	dfs = func(airport string) {
		for len(graph[airport]) > 0 {
			nextAirport := graph[airport][0]
			graph[airport] = graph[airport][1:]
			dfs(nextAirport)
		}
		result = append([]string{airport}, result...)
	}

	dfs("JFK")
	return result
}
